1. Field of the Invention
The present invention relates to an information filtering technology, in particular, to a banner advertisement selecting method for selecting a banner advertisement suitably displayed on each web page of the world wide web (WWW) of the Internet.
2. Description of the Related Art
The WWW is a collection of linked documents stored in information transmitting systems and their server systems on the Internet exchanged using the Hypertext Transfer Protocol (HTTP). The WWW may be simply referred to as web. These documents include text, images, video, and sound that are referred to as multi media or hyper text. In the WWW, these documents described in the Hyper Text Markup Language (HTML) are stored in the servers at web sites on the Internet. To browse documents of web sites in the world, special software termed web browser is used.
A banner advertisement displayed on a web page is selected corresponding to information that is transmitted in association with a home page browsing request or a keyword searching request (for example, the search keyword, the user domain name, the user ID, and the date), information of a browsed page (for example, the contents of the page, keywords, and categories), and user information (for example, past browsed pages and favorite fields).
To narrow banner advertisements using such information, several methods have been used. As one method, a rule is directly designated. As another method, the favorites of the user are learnt corresponding to his or her past click history. Corresponding to the learnt result, a user""s favorite banner advertisement is predicted and selected. These methods are known as xe2x80x9cAdForcexe2x80x9d (AdForce Company), xe2x80x9cAdKnowledgexe2x80x9d (AdKnowledge Company), xe2x80x9cDARTxe2x80x9d (Double Click Company), xe2x80x9cSelect Cast for Ad Servers (Aptex Company), and so forth.
In addition, there are many methods for clustering words and attributes. For example, a method for clustering words using minimum description length method has been disclosed by Ri and Abe as Japanese Patent Application No. 09-306966 xe2x80x9cAutomatic Word Classifying Apparatus and Automatic Word Classifying Methodxe2x80x9d. However, so far, a method for clustering search keywords and page attributes corresponding to the past click history and effectively selecting advertisements has not been disclosed.
Gittins Index is known as a ramification of the theorem of Bayes. According to Gittins Index, when a banner advertisement is selected, if there are a plurality of alternatives with unknown success probabilities, an optimum alternative is obtained corresponding to the number of successes and the number of fails in past attempts. For details of Gittins Index, refer to xe2x80x9cMulti-armed bandit allocation indicesxe2x80x9d by J. C. Gittins, John Wiley and Sons, 1988. However, the concept of Gittins Index has not been effectively used for selecting a banner advertisement in such a manner that the click rate becomes maximum in various constraints.
As described above, in the related art references, banner advertisements suitable for individual pages and users can be displayed. However, they do not have functions for detecting the number of display times of banner advertisements and the number of click times thereof and for effectively selecting a banner advertisement on balance.
In addition, to select a banner advertisement, the related art references do not have functions for clustering attribute values with a similar click history and reducing the number of learning parameters corresponding to search keywords and attributes of a browsing page. Thus, the learning speed is not high.
Moreover, the related art references do not optimally solve the tradeoff of the selection of various advertisements for improving the estimation accuracy of the click rate and the selection of advertisements with high click rate.
An object of the present invention is to provide a banner advertisement selecting method that allows restrictions such as a contracted number of display times and a contracted number of click times to be satisfied with data of the number of display times of a banner advertisement and the number of click times thereof and a banner advertisement to be selected in such a manner that the total click rate becomes high. In addition, an object of the present invention is to provide a method that allows the above-described problems to be solved and a high click rate to be accomplished with small amount of data.
The present invention is a banner advertisement selecting method for selecting a banner advertisement displayed on a page browsed through the world wide web (WWW) from an attribute list obtained corresponding to information transmitted with a page browsing request, information of the browsed page, and user information, the method comprising the steps of (a) estimating the input probability of each attribute and the click rate of each advertisement for each attribute corresponding to an input attribute distribution of the banner advertisement and a click history of which the banner advertisement was clicked, (b) obtaining a display probability of each banner advertisement for each attribute so that the total click rate becomes maximum with conditions such as the desired number of display times of each banner advertisement being satisfied, (c) selecting a banner advertisement according to the display probability, and (d) transforming a constrained objective function maximizing problem obtained at step (b) to a transportation problem and solving the transportation problem.
The banner advertisement selecting method further comprises the steps of (e) clustering attributes with similar click histories, step (e) being followed by step (b), (f) obtaining a cluster to which the input attribute belongs, and (g) selecting a banner advertisement to be displayed according to the display probability of each banner advertisement for the cluster.
Step (b) is performed by treating step (e) as a problem for estimating a click rate conditioned with each attribute using a past click rate history for each attribute, and repeatedly combining attributes that causes the total description length to be minimized or sub-minimized using a greedy heuristic based on the theory of minimum description length so as to decrease the number of estimation parameters and improve the estimation accuracy.
Step (b) is performed by treating step (e) as a problem for estimating a click rate conditioned with each attribute using a past click rate history for each attribute, and repeatedly combining attributes that causes the total information amount to be minimized or sub-minimized using a greedy heuristic based on Akaike information criterion so as to decrease the number of estimation parameters and improve the estimation accuracy.
The banner advertisement selecting method further comprises the step of securing a large value as the minimum display probability that is inversely proportional to the square root of the number of display times of each banner advertisement with each attribute.
The banner advertisement selecting method further comprises the steps of calculating estimation value c of the click rate for each banner advertisement j with each attribute i using the number of display times and the number of click times, obtaining estimation value xcexc of the click rate for attribute i of past banner advertisement jxe2x80x2 having attributes similar to the attribute of banner advertisement j, adding 1 to the number of display times of banner advertisement j with attribute i, and calculating estimation value c of the click rate with a value of which xcexc is added to the number of click times.
In the banner advertisement selecting method, Gittins Index or compensated Gittins Index compensated by Laplace estimation is used instead of the estimation value of the click rate that forms the maximized objective function.
The banner advertisement selecting method further comprises the step of randomly selecting one attribute from a plurality of input attributes, and selecting a banner advertisement to be displayed according to the display probability of each banner advertisement with the selected attribute.
Step (c) is performed by clustering attributes with similar click history, securing the minimum display probability inversely proportional to the square root of the number of display times of an advertisement against an attribute, adding a click rate estimated from a past advertisement that is similar to the relevant advertisement to the number of click times, estimating the resultant value with Gittins Index, transforming a constrained objective function optimizing problem to a transportation problem, and applying the solution of the transportation problem to calculate an optimal display probability of each banner advertisement for each attribute.
Step (c) is performed by selecting one from a plurality of input attributes at random, obtaining a cluster to which the selected attribute belongs, and selecting a banner advertisement according to the display probability of each advertisement against the obtained cluster.